<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN"
            "http://www.w3.org/TR/REC-html40/loose.dtd">
<HTML>
<HEAD>



<META http-equiv="Content-Type" content="text/html; charset=ISO-8859-1">
<META name="GENERATOR" content="hevea 1.08">
<LINK rel="stylesheet" type="text/css" href="tutorial.css">
<TITLE>
CHR
</TITLE>
</HEAD>
<BODY >
<A HREF="tutorial110.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial112.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
<HR>

<H2 CLASS="section"><A NAME="htoc218">15.4</A>&nbsp;&nbsp;CHR</H2><UL>
<LI><A HREF="tutorial111.html#toc109">How to Use CHR</A>
<LI><A HREF="tutorial111.html#toc110">Multiple Heads</A>
</UL>

<A NAME="secchr"></A>
<A NAME="@default398"></A>
Constraint Handling Rules were originally implemented in ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP>.
They are introduced in the paper [<A HREF="tutorial133.html#Fruehwirth"><CITE>9</CITE></A>].<BR>
<BR>
<A NAME="toc109"></A>
<H3 CLASS="subsection"><A NAME="htoc219">15.4.1</A>&nbsp;&nbsp;How to Use CHR</H3>
<A NAME="@default399"></A>
<A NAME="@default400"></A>
CHR's offer a rule-based programming style to express constraint
simplification and constraint propagation.
The rules all have a <EM>head</EM>, an explicit or implicit <EM>guard</EM>,
and a <EM>body</EM>, and are written either
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
Head &lt;=&gt; Guard | Body.  %Simplification Rule
</PRE></BLOCKQUOTE>
or
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
Head ==&gt; Guard | Body.   %Propagation Rule
</PRE></BLOCKQUOTE>
When a constraint is posted that is an instance of the head, the guard
is checked to determine whether the rule can fire.
If the guard is satisfied (i.e. CHR detects that it is entailed by the
current search state), the 
rule <EM>fires</EM>. 
Unlike ECL<SUP><I>i</I></SUP>PS<SUP><I>e</I></SUP> clauses, the rules leave no choice points.
Thus if several rules share the same head and one fires, the other
rules are never fired even after a failure.<BR>
<BR>
Normally the guards exclude each other, as in the <CODE>noclash</CODE>
example:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- lib(ech).
:- constraints noclash/2.
noclash(S1,S2) &lt;=&gt; ic:(S2 #&lt; S1+5) | ic:(S1 #&gt;= S2+5).
noclash(S1,S2) &lt;=&gt; ic:(S1 #&lt; S2+5) | ic:(S2 #&gt;= S1+5).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Henceforth we will not explicitly load the <TT>ech</TT> library.<BR>
<BR>
The power of guards lies in the behaviour of the rules when they are
neither entailed, nor disentailed.
Thus in the query
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- ic:([S1,S2]::1..10),
   noclash(S1,S2),
   S1 #&gt;= 6.
</PRE></BLOCKQUOTE>

when the <CODE>noclash</CODE> constraint is initially posted, neither guard
is entailed, and CHR simply postpones the handling of the constraint
until further constraints are posted.
As soon as a guard becomes entailed, however, the rule fires.
For simplification rules, of the form 
<CODE>Head &lt;=&gt; Guard | Body</CODE>, 
the head is replaced by the body.
In this example, therefore, <CODE>noclash(S1,S2)</CODE> is replaced by
<CODE>S1 #&gt;= S2+5</CODE>.
<BR>
<BR>
Propagation rules are useful to add constraints, instead of replacing
them.
Consider, for example, an application to temporal reasoning.
If the time <I>T</I>1 is before time <I>T</I>2, then we can propagate an
additional <I>ic</I> constraint saying <I>T</I>1 =&lt; <I>T</I>2:

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- constraints before/2.
before(T1,T2) ==&gt; ic:(T1 $=&lt; T2)
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
This rule simply posts the constraint <CODE>T1 $=&lt; T2</CODE> to <I>ic</I>.
When a propagation rule fires its body is invoked, but its head
remains in the constraint store.<BR>
<BR>
<A NAME="toc110"></A>
<H3 CLASS="subsection"><A NAME="htoc220">15.4.2</A>&nbsp;&nbsp;Multiple Heads</H3>
Sometimes different constraints interact, and more can be deduced
from the combination of constraints than can be deduced from the
constraints separately. Consider the following query:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
?- ic:([S1,S2]::1..10),
   noclash(S1,S2),
   before(S1,S2).
</PRE></BLOCKQUOTE>
Unfortunately the <TT>ic</TT> bounds are not tight enough for the
<CODE>noclash</CODE> rule to fire.
The two constraints can be combined so as to propagate <I>S</I>2 &#8805; <I>S</I>1+5
using a two-headed
CHR:
<BLOCKQUOTE CLASS="quote">
<PRE CLASS="verbatim">
noclash(S1,S2), before(S1,S2) ==&gt; ic:(S2 #&gt;= S1+5).
</PRE></BLOCKQUOTE>
We would prefer to write a set of rules that captured this kind of
inference in a general way.<BR>
<BR>
<A NAME="@default401"></A>
This can be achieved by writing a more complete solver for
<CODE>prec</CODE>, and combining it with <CODE>noclash</CODE>.
<I>prec</I>(<I>S</I>1,<I>D</I>,<I>S</I>2) holds if the time <I>S</I>1 precedes the time <I>S</I>2 by at
least <I>D</I> units of time.
For the following code to work, <I>S</I>1 and <I>S</I>2 may be numbers or
variables, but <I>D</I> must be a number.

	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#CCCCFF">
	<BLOCKQUOTE CLASS="quote"><PRE>
:- constraints prec/3.
prec(S,D,S) &lt;=&gt; D=&lt;0.
prec(S1,0,S2), prec(S2,0,S1) &lt;=&gt; S1=S2.
prec(S1,D1,S2), prec(S2,D2,S3) ==&gt; D3 is D1+D2, prec(S1,D3,S3).
prec(S1,D1,S2) <CODE>\</CODE> prec(S1,D2,S2) &lt;=&gt; D2=&lt;D1 | true.     % Simpagation

noclash(S1,S2), prec(S1,D,S2) ==&gt; D &gt; -5 | prec(S1,5,S2).
noclash(S1,S2), prec(S2,D,S1) ==&gt; D &gt; -5 | prec(S2,5,S1).
</PRE></BLOCKQUOTE></TD>
</TR></TABLE>
Note the <EM>simpagation</EM> rule, whose head has two parts 
<CODE>Head1 \ Head2</CODE>. 
In a simpagation rule <CODE>Head2</CODE> is replaced, but <CODE>Head1</CODE> is
kept in the constraint store.<BR>
<BR>

	<BLOCKQUOTE CLASS="figure"><DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV>
	<DIV CLASS="center">
	<TABLE CELLPADDING=10>
<TR><TD BGCOLOR="#DB9370">
	
CHRs are guarded rules which fire without leaving choice points.
A CHR rule may have one or many goals in the head, and may take the
following forms: Simplification rule, Propagation rule or Simpagation
rule. 
<BR>
<BR>

	</TD>
</TR></TABLE>
	</DIV>
	<BR>
<BR>
<DIV CLASS="center">Figure 15.5: CHRs</DIV><BR>
<BR>

	<DIV CLASS="center"><HR WIDTH="80%" SIZE=2></DIV></BLOCKQUOTE>
<HR>
<A HREF="tutorial110.html"><IMG SRC ="previous_motif.gif" ALT="Previous"></A>
<A HREF="tutorial107.html"><IMG SRC ="contents_motif.gif" ALT="Up"></A>
<A HREF="tutorial112.html"><IMG SRC ="next_motif.gif" ALT="Next"></A>
</BODY>
</HTML>
